package it.unisa.ingegneria.tdp.esercitazione3;
import java.util.Iterator;


public class LinkedBinaryTree<E extends Comparable<E>> implements BinaryTree<E> {

	protected int size;
	protected BTPosition<E> root;
	
	public LinkedBinaryTree(){
		size = 0;
		root = null;
	}
	
	
	public int size() {
		return size;
	}

	
	public boolean isEmpty() {
		return (size()==0);
	}

	
	protected void preorderPositions(Position<E> v, PositionList<Position<E>> pos) throws InvalidPositionException, BoundaryViolationException {

		pos.addLast(v);

			if (hasLeft(v) && left(v).element()!=null){
				preorderPositions(left(v), pos);
			}
			if (hasRight(v) && right(v).element()!=null){
				preorderPositions(right(v), pos);
			}
	}

	
	// positions() restituisce una collezione iterabile delle posizioni di tutti gli elementi dell'albero
	public Iterable<Position<E>> positions() {
		PositionList<Position<E>> positions = new NodePositionList<Position<E>>();
		
		if(size!=0){
			try {
				preorderPositions(root(), positions);
			} catch (InvalidPositionException | BoundaryViolationException
					| EmptyTreeException e) {
				e.printStackTrace();
			}
		}
		
		return positions;
	}


	public E replace(Position<E> v, E e) throws InvalidPositionException {
		BTPosition<E> vv = checkPosition(v);
		E temp = v.element();
		vv.setElement(e);
		
		return temp;
	}


	public Position<E> root() throws EmptyTreeException {
		if (root == null)
			throw new EmptyTreeException("The tree is empty");
		
		return root;
	} 


	public Position<E> parent(Position<E> v) throws InvalidPositionException,
			BoundaryViolationException {

		BTPosition<E> vv = checkPosition(v);
		Position<E> parentPos = vv.getParent();
		
		if(parentPos == null)
			throw new BoundaryViolationException("Non esiste genitore.");
		
		return parentPos;
	}


	public Iterable<Position<E>> children(Position<E> v)
			throws InvalidPositionException {

		PositionList<Position<E>> children = new NodePositionList<Position<E>>();
		
		try {
			if(hasLeft(v)){
				children.addLast(left(v));
			}
			
			if(hasRight(v)){
				children.addLast(right(v));
			}
		} catch (BoundaryViolationException e) {
			e.printStackTrace();
		}
		
		return children;
	}


	public boolean isInternal(Position<E> v) throws InvalidPositionException {
		checkPosition(v);
		return (hasLeft(v) || hasRight(v));
	}


	public boolean isExternal(Position<E> v) throws InvalidPositionException {
		checkPosition(v);
		return (!hasLeft(v) && !hasRight(v));
	}


	public boolean isRoot(Position<E> v) throws InvalidPositionException {
		boolean isRoot = false;
		
		checkPosition(v);
		
		try {
			isRoot = (v == root());
		} catch (EmptyTreeException e) {
			e.printStackTrace();
		}
		
		return isRoot;
	}

	
	// iterator() restituisce un iteratore degli elementi memorizzati nei nodi dell'albero
	public Iterator<E> iterator() {
		Iterable<Position<E>> positions = positions();
		
		PositionList<E> elements = new NodePositionList<E>();
		Iterator<Position<E>> it = positions.iterator();
		
		while(it.hasNext()){
			try {
				elements.addLast(it.next().element());
			} catch (InvalidPositionException e) {
				e.printStackTrace();
			}
		}
		
		return elements.iterator();
	}


	public Position<E> left(Position<E> v) throws InvalidPositionException, BoundaryViolationException { 
		BTPosition<E> vv = checkPosition(v);
		Position<E> leftPos = vv.getLeft();
		
		if (leftPos == null)
			throw new BoundaryViolationException(" Nessun figlio sinistro.");
		
		return leftPos;
	}


	public Position<E> right(Position<E> v) throws InvalidPositionException, BoundaryViolationException { 
		BTPosition<E> vv = checkPosition(v);
		Position<E> rightPos = vv.getRight();
		
		if (rightPos == null)
			throw new BoundaryViolationException("Nessun figlio destro.");
		
		return rightPos;
	}


	public boolean hasLeft(Position<E> v) throws InvalidPositionException {
		BTPosition<E> vv = checkPosition(v);
		
		return (vv.getLeft() != null);
	}


	public boolean hasRight(Position<E> v) throws InvalidPositionException {
		BTPosition<E> vv = checkPosition(v);
		
		return (vv.getRight() != null);
	}
	
	
	public Position<E> sibling(Position<E> v) throws InvalidPositionException, BoundaryViolationException{
		
		BTPosition<E> vv = checkPosition(v);
		BTPosition<E> parentPos = vv.getParent();
		
		if(parentPos != null){
			BTPosition<E> sibPos;
			BTPosition<E> leftPos = parentPos.getLeft();
			
			if(leftPos == vv){
				sibPos = parentPos.getRight();
			}else{
				sibPos = parentPos.getLeft();
			}
			if(sibPos != null){
				return sibPos;
			}
		}
		
		throw new BoundaryViolationException("Non esiste un nodo fratello.");
	}
	
	
	public Position<E> addRoot(E e) throws NonEmptyTreeException{
		if(!isEmpty())
			throw new NonEmptyTreeException("L'albero ha gia' una radice.");
		
		size = 0;
		root = createNode(e, null, null, null);
		
		return root;
	}
	
	
	public Position<E> insertLeft(Position<E> v, E e) throws InvalidPositionException{
		
		BTPosition<E> vv = checkPosition(v);
		Position<E> leftPos = vv.getLeft();
		
		if(leftPos!=null)
			throw new InvalidPositionException("Il nodo ha gia' un figlio sinistro.");
		
		BTPosition<E> ww = createNode(e, vv, null, null);
		vv.setLeft(ww);
		//size++;
		
		return ww;
	}
	
	
	public Position<E> insertRight(Position<E> v, E e) throws InvalidPositionException{
		
		BTPosition<E> vv = checkPosition(v);
		Position<E> rightPos = vv.getRight();
		
		if(rightPos!=null)
			throw new InvalidPositionException("Il nodo ha gia' un figlio destro.");
		
		BTPosition<E> ww = createNode(e, vv, null, null);
		vv.setRight(ww);
		//size++;
		
		return ww;
	}
	
	
	public E remove(Position<E> v) throws InvalidPositionException{
		
		BTPosition<E> vv = checkPosition(v);
		BTPosition<E> leftPos = vv.getLeft();
		BTPosition<E> rightPos = vv.getRight();
		
		if(leftPos!=null && rightPos!=null)
			throw new InvalidPositionException("Non e' possibile rimuovere un nodo con due figli.");
		
		// ww e' l'unico figlio presente
		BTPosition<E> ww;
		if(leftPos!=null){
			ww = leftPos;
		}else if(rightPos!=null){
			ww = rightPos;
		}else{
			ww = null;				// v e' un nodo foglia
		}
		
		if(vv==root){				// v e' la radice
			if(ww!=null){
				ww.setParent(null);
			}
			
			root = ww;
		}else{
			BTPosition<E> uu = vv.getParent();
			if(vv==uu.getLeft()){
				uu.setLeft(ww);
			}else{
				uu.setRight(ww);
			}
			
			if(ww!=null){
				ww.setParent(uu);
			}
		}
		
		size--;
		
		return v.element();
	}
	
	
	protected BTPosition<E> checkPosition(Position<E> v) throws InvalidPositionException{
		if(v==null || !(v instanceof BTPosition))
			throw new InvalidPositionException("La posizione non e' valida.");
			
		return (BTPosition<E>) v;
	}
	
	protected BTPosition<E> createNode(E element, BTPosition<E> parent, BTPosition<E> left, BTPosition<E> right){
		return new BTNode<E>(element, parent, left, right);
	}
	
	
	protected void expandExternal(Position<E> v, E l, E r) throws InvalidPositionException {
		if (!isExternal(v))
			throw new InvalidPositionException("Il nodo non e` una foglia.");
		
		insertLeft(v, l);
		insertRight(v, r);
		size++;
	}
	
	public void setRoot(BTPosition<E> e){
		this.root=e;
	}
	
}
